/**
 * 1448. 统计二叉树中好节点的数目
 * https://leetcode-cn.com/problems/count-good-nodes-in-binary-tree/
 */
public class Solutions_1448 {
    public static void main(String[] args) {
        String str = "[3 1 4 3 # 1 5]";  // output: 4
//        String str = "[3 3 # 4 2]";  // output: 3
//        String str = "[1]";  // output: 1

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        int result = goodNodes(root);
        System.out.println(result);
    }

    private static int res = 0;
    public static int goodNodes(TreeNode root) {
        res = 0;
        dfs(root, Integer.MIN_VALUE);
        return res;
    }

    public static void dfs(TreeNode root, int max) {
        if (root == null) {
            return;
        }
        // root 节点，是一个好节点：从根节点到 root 节点组成的路径上的最大值
        if (root.val >= max) {
            res ++;
        }
        // 记录下路径上的最大值比较最大值
        max = Math.max(max, root.val);
        // 继续
        dfs(root.left, max);
        dfs(root.right, max);
    }
}
